use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

struct Solution;

impl Solution {
    //     自己实现
//     pub fn get_all_elements(root1: Option<Rc<RefCell<TreeNode>>>, root2: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
//         let list = Rc::new(RefCell::new(vec![]));
//         Solution::traverse_tree(root1, list.clone());
//         Solution::traverse_tree(root2, list.clone());
//         let mut vec = Rc::try_unwrap(list).ok().unwrap().into_inner();
//         vec.sort();
//         vec
//     }

//     // 遍历树
//     fn traverse_tree(root: Option<Rc<RefCell<TreeNode>>>, list: Rc<RefCell<Vec<i32>>>) {
//         if let Some(root_rc) = root {
//             list.borrow_mut().push(root_rc.borrow().val);
//             Solution::traverse_tree(root_rc.borrow().left.clone(), list.clone());
//             Solution::traverse_tree(root_rc.borrow().right.clone(), list);
//         }
//     }


    pub fn get_all_elements(root1: Option<Rc<RefCell<TreeNode>>>, root2: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut vec = vec![];
        let mut root1_vec = vec![];
        let mut root2_vec = vec![];
        Solution::dfs(root1, &mut root1_vec);
        Solution::dfs(root2, &mut root2_vec);
        let mut i = 0;
        let mut j = 0;
        while i < root1_vec.len() || j < root2_vec.len() {
            if j == root2_vec.len() || i < root1_vec.len() && root1_vec.get(i) < root2_vec.get(j) {
                vec.push(*root1_vec.get(i).unwrap());
                i += 1;
            } else if j < root2_vec.len() {
                vec.push(*root2_vec.get(j).unwrap());
                j += 1;
            }
        }
        vec
    }

    fn dfs(root: Option<Rc<RefCell<TreeNode>>>, vec: &mut Vec<i32>) {
        if let Some(root_rc) = root {
            Solution::dfs(root_rc.borrow().left.clone(), vec);
            vec.push(root_rc.borrow().val);
            Solution::dfs(root_rc.borrow().right.clone(), vec);
        }
    }
}


fn main() {
    Solution::get_all_elements(None, None);
}
